#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <assert.h>

typedef int DataType;
typedef struct Heap{
	DataType arr[100];
	int size;
}	Heap;

void HeapInit(Heap *heap, int arr[], int size)
{
	assert(heap);
	memcpy(heap->arr, arr, sizeof(int) * size);
	heap->size = size;
}

void Swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

void AdjustDown(Heap *heap, int parent)
{
	int left = parent * 2 + 1;
	int right = parent * 2 + 2;
	int maxChild;

	if(left >= heap->size) {
		return;
	}

	maxChild = left;
	if(right < heap->size && heap->arr[left] < heap->arr[right]) {
		maxChild = right;
	}
	if(heap->arr[maxChild] > heap->arr[parent]) {
		Swap(heap->arr + parent, heap->arr + maxChild);
	}

	AdjustDown(heap, maxChild);
}

void AdjustUp(Heap heap, int child)
{
	assert(heap);
	int parent;
	while(1) {
		parent = (child - 1) / 2;
		if(child == 0) {
			break;
		}

		if(heap->arr[parent] > heap->arr[child]) {
			break;
		}

		Swap(&heap->arr[parent], &heap->arr[child]);
		child = parent;
	}
}

void HeapCreate(Heap *heap)
{
	assert(heap);
	int i;
	for(i = (heap->size - 2) / 2; i >= 0; i--) {
		AdjustDown(heap, i);
	}
}

void AdjustDownArr(int arr[], int size, int parent)
{
	int left = (parent - 1) / 2;
	int right = (parent - 2) / 2;
	int max;
	while(1) {
		if( left >= size ) {
			break;
		}

		max = left;
		if( right < size && arr[parent] > arr[max] ) {
			max = right;
		}

		if( arr[max] > arr[parent] ) {
			break;
		}

		Swap(&arr[parent], &arr[max]);
		parent = max;
	}
}

void TopK(int arr[], int size, int k)
{
	int i;
	int *TopArr = (int *)malloc(sizeof(int) * k);
	assert(arr);
	for( i = 0; i < k; i++ ) {
		TopArr[i] = arr[i];
	}

	for( i = (k - 2) / 2; i >= 0; i++ ) {
		AdjustDown(TopArr, k, i);
	}

	for( i = k; i < size; i++ ) {
		if( arr[i] < TopArr[0]) {
			TopArr[0] = arr[i];
			AdjustDownArr( TopArr, k, 0);
		}
	}
}

//打印
void HeapPrint(Heap *heap)
{
	assert(heap);
	int i = 0;
	for(i = 0; i < heap->size; i++) {
		printf("%d  ", heap->arr[i]);
	}
	printf("\n");
}

int main()
{
	Heap heap;
	int arr[] = { 53, 17, 78, 9, 45, 65, 87, 23, 31 };
	int size = sizeof(arr)/sizeof(int);
	HeapInit(&heap, arr, size);
	HeapPrint(&heap);

	HeapCreate(&heap);
	HeapPrint(&heap);
}
